package com.likou;

public class Demo001_省份数量_朋友圈 {
    public static void main(String[] args) {
        int aa[][] = new int[][]{{1,1,0},{1,1,0},{0,0,1}} ;
        int circleNum = findCircleNum(aa);
        System.out.println(circleNum);
    }
    public static int findCircleNum(int[][] isConnected) {
        /**
         使用一个visited数组, 依次判断每个节点, 如果其未访问, 朋友圈数加1并对该节点进行dfs搜索标记所有访问到的节点
         **/
        boolean[] visited = new boolean[isConnected.length];
        int ret = 0;
        for(int i = 0; i < isConnected.length; ++i) {
            if(!visited[i]) {
                dfs(isConnected, visited, i);
                ret++;
            }
        }
        return ret;
    }

    private static void dfs(int[][] m, boolean[] visited, int i) {
        for(int j = 0; j < m.length; ++j) {
            if(m[i][j] == 1 && !visited[j]) {
                visited[j] = true;
                dfs(m, visited, j);
            }
        }
    }
  /*  public int findCircleNum(int[][] M) {
        int ans = 0;
        for(int i = 0;i<M.length;i++)
        {
            if(dfs(M,i)>0)
            {
                ans++;
            }
        }
        return ans;
    }
    int dfs(int[][] M,int i)
    {
        //遍历之后将对角线元素置0
        if(M[i][i] != 1)
            return 0;
        int ans = 1;
        M[i][i] = 0;
        for(int j = 0;j<M.length;j++)
        {
            if(M[i][j] == 1)
            {
                ans += dfs(M,j);
            }
        }
        return ans;
    }*/
}
